package org.lql.algo.codecrush.hot100.graphTheory;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author: liangqinglong
 * @date: 2025-09-15 23:43
 * @description: 207. 课程表 <a href="https://leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class CanFinish {

	List<List<Integer>> to;
	int[] inDegree;

	public boolean canFinish(int numCourses, int[][] prerequisites) {
		if (numCourses <= 0 || prerequisites == null) {
			// 如果课程数小于等于0或先决条件为空，则无法进行学习。
			return false;
		}
		to = new ArrayList<>();
		for (int i = 0; i < numCourses; i++) {
			to.add(new ArrayList<>());
		}
		inDegree = new int[numCourses];
		for (int[] prerequisite : prerequisites) {
			int ai = prerequisite[0];
			int bi = prerequisite[1];
			// 确定课程学习关系
			this.to.get(bi).add(ai);
			inDegree[ai]++;
		}
		List<Integer> lessons = new ArrayList<>();
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < numCourses; i++) {
			// 查找可以直接开始学习的课程进行入队
			if (inDegree[i] == 0) {
				queue.offer(i);
			}
		}
		while (!queue.isEmpty()) {
			// 待学习课程
			Integer lesson = queue.poll();
			// 表示已学习课程
			lessons.add(lesson);
			// 根据课程关系获取需要先学习的课程
			for (Integer needLesson : to.get(lesson)) {
				// 学习完一门课程，减少一个关系
				inDegree[needLesson]--;
				// 当没有需要先学习的课程时，表示可以进行学习
				if (inDegree[needLesson] == 0) {
					queue.offer(needLesson);
				}
			}
		}
		return lessons.size() == numCourses;
	}

	public static void main(String[] args) {
		CanFinish canFinish = new CanFinish();
		// true
		System.out.println(canFinish.canFinish(2, new int[][]{{1, 0}}));
		// false
		System.out.println(canFinish.canFinish(2, new int[][]{{1, 0}, {0, 1}}));
	}
}
